{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #搜索插入位置"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: searchInsert"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #搜索插入位置"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个排序的整数数组 <code>nums</code>&nbsp;和一个整数目标值<code> target</code> ，请在数组中找到&nbsp;<code>target&nbsp;</code>，并返回其下标。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。</p>\n",
    "\n",
    "<p>请必须使用时间复杂度为 <code>O(log n)</code> 的算法。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [1,3,5,6], target = 5\n",
    "<strong>输出:</strong> 2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [1,3,5,6], target = 2\n",
    "<strong>输出:</strong> 1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [1,3,5,6], target = 7\n",
    "<strong>输出:</strong> 4\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [1,3,5,6], target = 0\n",
    "<strong>输出:</strong> 0\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [1], target = 0\n",
    "<strong>输出:</strong> 0\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>-10<sup>4</sup> &lt;= nums[i] &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>nums</code> 为<strong>无重复元素</strong>的<strong>升序</strong>排列数组</li>\n",
    "\t<li><code>-10<sup>4</sup> &lt;= target &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 35&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/search-insert-position/\">https://leetcode-cn.com/problems/search-insert-position/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [N6YdxV](https://leetcode.cn/problems/N6YdxV/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [N6YdxV](https://leetcode.cn/problems/N6YdxV/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        left, right = 0, len(nums) #采用左闭右开区间[left,right)\n",
    "        while left < right: # 右开所以不能有=,区间不存在\n",
    "            mid = left + (right - left)//2 # 防止溢出, //表示整除\n",
    "            if nums[mid] < target: # 中点小于目标值,在右侧,可以得到相等位置\n",
    "                left = mid + 1 # 左闭,所以要+1\n",
    "            else:\n",
    "                right = mid # 右开,真正右端点为mid-1\n",
    "        return left # 此算法结束时保证left = right,返回谁都一样\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        for i,v in enumerate(nums):\n",
    "            if v>=target:\n",
    "                return i\n",
    "        return len(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "\n",
    "        low = 0\n",
    "        high = len(nums)\n",
    "        while low < high:\n",
    "            mid = low + ((high -low)>>1)\n",
    "            if nums[mid] == target:\n",
    "                high = mid\n",
    "            elif nums[mid] < target:\n",
    "                low = mid + 1\n",
    "            else:\n",
    "                high = mid\n",
    "        \n",
    "        return low"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        length = len(nums)\n",
    "        total = length\n",
    "        n = total//2\n",
    "        \n",
    "        if target > nums[length-1]:\n",
    "            return length\n",
    "\n",
    "        if target <= nums[0]:\n",
    "            return 0\n",
    "\n",
    "        while target != nums[n]:\n",
    "            if nums[n] < target and target < nums[n+1]:\n",
    "                return n+1\n",
    "\n",
    "            if target < nums[n] :\n",
    "                 total = total//2\n",
    "                 n = total//2\n",
    "            else:\n",
    "                total = math.ceil(total/2)\n",
    "                n = math.ceil((total)/2) + n \n",
    "                \n",
    "        return n\n",
    "         \n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        return bisect.bisect_left(nums,target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        l = 0\n",
    "        r = n\n",
    "        while l < r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if nums[mid] < target:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        return r\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        from bisect import bisect_left\n",
    "        return bisect_left(nums,target)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        return bisect_right(nums, target-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        l=0\n",
    "        r=len(nums)-1\n",
    "        while l<=r:\n",
    "            mid=(l+r)//2\n",
    "            if nums[mid]>target:\n",
    "                r=mid-1\n",
    "            else:\n",
    "                l=mid+1\n",
    "        return r if target==nums[r] else r+1  #r找出来的位置肯定是<=target的，因此r最终的位置要么是target，要么是<target的值"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        l=0\n",
    "        r=len(nums)-1\n",
    "        if nums[r]<target:\n",
    "            return len(nums)\n",
    "        while l<r:\n",
    "            m=(l+r)//2\n",
    "            if nums[m]<target:\n",
    "                l=m+1\n",
    "            elif nums[m]>=target:\n",
    "                r=m\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        l = 0\n",
    "        r = n\n",
    "        while l < r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if nums[mid] < target:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        return r\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        l,r=0,len(nums)\n",
    "        while l < r:\n",
    "            mid=((r-l)>>1)+l\n",
    "            if nums[mid]==target:\n",
    "                return mid\n",
    "            elif nums[mid] < target:\n",
    "                l=mid+1\n",
    "            else:\n",
    "                r=mid\n",
    "        return l\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        for k, v in enumerate(nums):\n",
    "            if target == v:\n",
    "                return k\n",
    "            elif target < v:\n",
    "                return k\n",
    "        \n",
    "        return len(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        l, r = 0, n\n",
    "        \n",
    "        while l < r:\n",
    "            mid = l + (r-l)//2\n",
    "            if nums[mid] == target:\n",
    "                return mid\n",
    "            elif nums[mid] < target:\n",
    "                l = mid + 1\n",
    "            elif nums[mid] > target:\n",
    "                r = mid\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        left = 0\n",
    "        right = len(nums)-1\n",
    "        if target<nums[left]:\n",
    "            return 0\n",
    "        if target>nums[right]:\n",
    "            return right+1\n",
    "        \n",
    "        while left<=right:\n",
    "            mid = (left+right) >> 1\n",
    "            if nums[mid] == target:\n",
    "                return mid\n",
    "            elif nums[mid] > target:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        # 二分查找，库函数bisect\n",
    "        from bisect import bisect_left\n",
    "        idx = bisect_left(nums, target)\n",
    "        return idx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        left, right = 0, n - 1\n",
    "        while right >= left:\n",
    "            mid = (left + right) // 2\n",
    "            if target == nums[mid]:\n",
    "                return mid\n",
    "            elif nums[mid] > target:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def searchInsert(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # 初始化左边界和右边界\n",
    "        left, right = 0, len(nums)-1\n",
    "        # 只要左边界小于等于右边界均可进行二分查找当左边界大于右边界时显然当前要查找的值不在数组中\n",
    "        while left<=right:\n",
    "            # 数组元素个数可能为奇数，取整除\n",
    "            md = (left+right)//2\n",
    "            # 若当前二分查找的中间位置元素刚好是要找的，直接返回\n",
    "            if nums[md]==target:\n",
    "                return md\n",
    "            # 否则，若中间位置的元素大于目标值，则应当从较小的一半数组中查找，故右边界更新为md-1\n",
    "            # 由于md本身大于target，故不需要考虑md位置的元素，所以是md-1\n",
    "            elif nums[md]>target:\n",
    "                right = md-1\n",
    "            # 同理，若中间位置元素小于目标值，应当从较大的一半数组中查找，故更新左边界为md+1\n",
    "            else:\n",
    "                left = md+1\n",
    "        # 左边界即为待插入的位置\n",
    "        return right+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        if nums[0] >= target: return 0\n",
    "        if nums[-1] < target: return len(nums)\n",
    "        left, right = 0, len(nums) - 1\n",
    "        while left <= right:\n",
    "            md = (left + right) // 2\n",
    "            if nums[md] == target:\n",
    "                return md\n",
    "            elif nums[md] > target:\n",
    "                right = md - 1\n",
    "            else:\n",
    "                left = md + 1\n",
    "        return left "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        l = 0\n",
    "        r = len(nums)\n",
    "        while l < r:\n",
    "            mid = l + (r-l) // 2\n",
    "            if nums[mid] < target:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        left = 0\n",
    "        right = len(nums) - 1\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if nums[mid] < target:\n",
    "                left = mid + 1\n",
    "            elif nums[mid] > target:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                return mid\n",
    "        \n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        return bisect.bisect_left(nums, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 满足二分查找的前提，即有序数组+无重复元素+返回下标，但是和二分法不同的是，之前的二分法只需要返回下标即可，但是这里的二分法还要求“如果不存在于数组则返回被插入的位置”，所以这里应该用左闭右开的写法，中间如果找到就return middle，while结束后return left。二分查找的时间复杂度为logn，满足这里的要求。\n",
    "\n",
    "# 左闭右开区间，边界条件为while left<right，赋值语句为if nums[middle] > target，right == middle，且right的初始位置为len(nums)(因为right不包含)\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        if len(nums) == 0:  # 注意这个别忘 # 1\n",
    "            return -1 # 2\n",
    "        left, right = 0, len(nums) # 3\n",
    "        while left < right: # 4\n",
    "            middle = left + (right - left) // 2 \n",
    "            # 注意取middle的方法要记住！！！且python中除除以2取除数的符号是\"//\"\n",
    "            if nums[middle] == target:  # 6 \n",
    "                return middle # 7\n",
    "            elif nums[middle] > target: # 返回左区间 # 8\n",
    "                right = middle # 9\n",
    "            else: # 返回右区间 # 10\n",
    "                left = middle + 1 # 11\n",
    "        return left   # 5\n",
    "         # 最后的return值表示如果没找到那么应该返回什么，这里因为要求返回插入位置的下标，所以返回left，否则对于常规二分法来说这里返回的应该是-1\n",
    "\n",
    "# 注意：对于仅要求返回下标的基础二分法来说，左闭右闭区间的写法和上面的区别是：right的初始位置为len(nums)-1(因为right包含)；边界条件为while left <= right；赋值语句为if nums[middle] > target，right == middle - 1(因为right包含)\n",
    "# 不论是写法1还是写法2，当nums[middle] < target，即要跳转到右区间时，赋值语句都应该为left=middle + 1(因为left一直都是被包含在区间内的)\n",
    "\n",
    "## 题目解读拓展：\n",
    "# 这道题可以完全照搬到其他延申题目上：即\"当target不在目标数组中时\"，返回左闭右开区间的左边界索引值，相当于“返回元素插入的索引位置”，等价于\"返回数组中大于等于target的最小元素的索引\"(升序排列时)，等价于“返回数组中小于target的元素的个数”\n",
    "\n",
    "## 二分法的几个注意点：第一是两种搜索区间对应的while边界条件和赋值语句；第二种是当target不Nums中的时候，返回Left代表的三种含义；还有就是当有序数组中有重复元素应该如何处理"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "\n",
    "    n = len(nums)\n",
    "    left_idx = 0\n",
    "    right_idx = n - 1\n",
    "       \n",
    "    if target < nums[left_idx]:\n",
    "        return left_idx\n",
    "    \n",
    "    elif target > nums[right_idx]:\n",
    "        return right_idx + 1\n",
    "\n",
    "    while left_idx < right_idx:\n",
    "        mid = left_idx + (right_idx - left_idx) // 2\n",
    "\n",
    "        if target > nums[mid]:\n",
    "            left_idx = mid + 1\n",
    "\n",
    "        elif target < nums[mid]:\n",
    "            right_idx = mid - 1\n",
    "        else:\n",
    "            return mid\n",
    "\n",
    "    if target > nums[left_idx]:\n",
    "        return left_idx + 1\n",
    "    else:\n",
    "        return left_idx\n",
    "      \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        i,j = 0,len(nums)\n",
    "        while i<j:\n",
    "            mid = (i+j)>>1\n",
    "            if nums[mid]>=target:\n",
    "                j = mid\n",
    "            else:\n",
    "                i = mid+1\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        start,end=0,len(nums)\n",
    "        \n",
    "        while(start<end):\n",
    "            mid=start+(end-start)//2\n",
    "            \n",
    "            if nums[mid]==target:\n",
    "                return mid\n",
    "            elif nums[mid]>target:\n",
    "                end=mid\n",
    "            else:\n",
    "                start=mid+1\n",
    "\n",
    "        \n",
    "        return mid if nums[mid]>target else mid+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        if target in nums:\n",
    "            return nums.index(target)\n",
    "        else:\n",
    "            nums.append(target)\n",
    "            nums.sort()\n",
    "            return nums.index(target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        \n",
    "        l,r=0,len(nums)-1\n",
    "        if nums[-1]<target:\n",
    "            return r+1\n",
    "        if nums[0]>target:\n",
    "            return 0\n",
    "        while l<r:\n",
    "            mid=(l+r)//2\n",
    "            if nums[mid]>target:\n",
    "                r=mid\n",
    "            elif nums[mid]<target:\n",
    "                l=mid+1\n",
    "            else:\n",
    "                return mid\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        left, right = 0, len(nums)-1\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if nums[mid] == target:\n",
    "                return mid\n",
    "            elif nums[mid] > target:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        left, right = 0, len(nums) - 1\n",
    "        ans = len(nums)\n",
    "        while left <= right:\n",
    "            mid = (right + left) // 2\n",
    "            if nums[mid] < target:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "                ans = mid\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "\n",
    "        left,right = 0,len(nums)-1\n",
    "        while left<=right:\n",
    "            mid = (left+right)//2\n",
    "            if nums[mid]==target:\n",
    "                return mid\n",
    "            if nums[mid]>target:\n",
    "                right = mid-1\n",
    "            else:\n",
    "                left = mid +1 \n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        left, right = 0, len(nums)-1\n",
    "        while left <= right:\n",
    "            mid = (left+right) // 2\n",
    "            if nums[mid] == target:\n",
    "                return mid\n",
    "            if nums[mid] > target:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        for i in range(0,len(nums)):\n",
    "            if nums[i] >=target :\n",
    "                return i\n",
    "        return len(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "import bisect\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        return bisect.bisect_left(nums, target)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        left = 0\n",
    "        right = len(nums)\n",
    "        while left < right:\n",
    "            mid = (left + right) //2\n",
    "            if nums[mid] < target:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        try:\n",
    "            return nums.index(target)\n",
    "        except:\n",
    "            nums.append(target)\n",
    "            nums.sort()\n",
    "            return nums.index(target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        res = search(nums, target)\n",
    "        return res\n",
    "def search(nums, target):\n",
    "    left = 0\n",
    "    right = len(nums) - 1\n",
    "    while left <= right:\n",
    "        mid = left + (right - left) // 2\n",
    "        if nums[mid] == target:\n",
    "            right = mid - 1\n",
    "        elif nums[mid] < target:\n",
    "            left = mid + 1\n",
    "        elif nums[mid] > target:\n",
    "            right = mid - 1\n",
    "    return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        for i in range(0,len(nums)):\n",
    "            if nums[i] >=target :\n",
    "                return i\n",
    "        return len(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] >= target:\n",
    "                return i\n",
    "        return len(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        # 数组双指针：二分查找\n",
    "        left, right = 0, len(nums) - 1\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if nums[mid] > target:\n",
    "                right = mid - 1\n",
    "            elif nums[mid] < target:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                return mid\n",
    "        return right + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        left, right = 0, len(nums)-1\n",
    "        while left <= right:\n",
    "            mid = (left+right) // 2\n",
    "            if nums[mid] >= target:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "       n = len(nums)\n",
    "       if target < nums[0]:\n",
    "           return 0\n",
    "       if target > nums[n-1]:\n",
    "           return n\n",
    "       for i in range(n):\n",
    "           if target <= nums[i]:\n",
    "               return i\n",
    "       return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "            left, right = 0, len(nums)\n",
    "            while left < right:\n",
    "                mid = (left + right) >> 1\n",
    "                if nums[mid] == target:\n",
    "                   return mid\n",
    "                elif nums[mid] > target:\n",
    "                    right = mid\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        # 二分查找，库函数bisect\n",
    "        # from bisect import bisect_left\n",
    "        # idx = bisect_left(nums, target)\n",
    "        # return idx\n",
    "\n",
    "        # 二分查找，双指针\n",
    "        left, right = 0, len(nums) - 1\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if nums[mid] >= target:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        left  = 0\n",
    "        right = len(nums)\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if nums[mid] == target:\n",
    "                return mid\n",
    "            elif target > nums[mid]:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        left, right = 0, len(nums)-1\n",
    "        while left <= right:\n",
    "            mid = (left+right) // 2\n",
    "            if nums[mid] == target:\n",
    "                return mid\n",
    "            elif nums[mid] > target:\n",
    "                right = mid-1\n",
    "            else:\n",
    "                left = mid+1\n",
    "        return left\n",
    "\n",
    "       \n",
    "\n",
    "       \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        \n",
    "\n",
    "        if nums[-1] < target:\n",
    "            return n\n",
    "\n",
    "        if nums[0] >= target:\n",
    "            return 0\n",
    "\n",
    "        l, r = 0, n - 1\n",
    "        while l <= r:\n",
    "            mid = (r - l)//2 + l\n",
    "            if nums[mid] == target:\n",
    "                return mid\n",
    "            if nums[mid] > target and nums[mid - 1] < target:\n",
    "                return mid\n",
    "\n",
    "            if nums[mid] > target:\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        l = 0\n",
    "        r = len(nums) - 1\n",
    "        while r - l > 1:\n",
    "            mid = (l + r) // 2\n",
    "            if nums[mid ] >= target:\n",
    "                r = mid\n",
    "            elif nums[mid] < target:\n",
    "                l = mid\n",
    "        if nums[r] < target:\n",
    "            res = r + 1\n",
    "        elif nums[l] < target:\n",
    "            res = l + 1\n",
    "        else:\n",
    "            res = l\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        l = r = 0\n",
    "        if target in nums:\n",
    "            return nums.index(target)\n",
    "        else:\n",
    "            if target > nums[-1]:\n",
    "                return len(nums)\n",
    "            if target < nums[0]:\n",
    "                return 0\n",
    "            else:\n",
    "                a = [i for i,x in enumerate(nums) if x > target]\n",
    "                return a[0]\n",
    "\n",
    " \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "\n",
    "    n = len(nums)\n",
    "    left_idx = 0\n",
    "    right_idx = n - 1\n",
    "       \n",
    "    if target < nums[left_idx]:\n",
    "        return left_idx\n",
    "    \n",
    "    elif target > nums[right_idx]:\n",
    "        return right_idx + 1\n",
    "\n",
    "    while left_idx < right_idx:\n",
    "        mid = left_idx + (right_idx - left_idx) // 2\n",
    "\n",
    "        if target > nums[mid]:\n",
    "            left_idx = mid + 1\n",
    "\n",
    "        elif target < nums[mid]:\n",
    "            right_idx = mid - 1\n",
    "        else:\n",
    "            return mid\n",
    "\n",
    "    if target > nums[left_idx]:\n",
    "        return left_idx + 1\n",
    "    else:\n",
    "        return left_idx\n",
    "      \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        def binarySearch(i, j, target, nums):\n",
    "            while j - i > 3:\n",
    "                mid = (i + j) >> 1\n",
    "                if nums[mid] < target: i = mid + 1\n",
    "                else: j = mid\n",
    "            for k in range(i, j+1):\n",
    "                if nums[k] >= target:\n",
    "                    return k\n",
    "            return len(nums)\n",
    "        \n",
    "        pos = binarySearch(0, len(nums)-1, target, nums)\n",
    "        return pos"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "    left_idx = 0\n",
    "    right_idx = len(nums) - 1\n",
    "       \n",
    "    if target < nums[left_idx]:\n",
    "        return left_idx\n",
    "    \n",
    "    elif target > nums[right_idx]:\n",
    "        return right_idx + 1\n",
    "\n",
    "    while left_idx < right_idx:\n",
    "        mid = (right_idx + left_idx) // 2\n",
    "\n",
    "        if target > nums[mid]:\n",
    "            left_idx = mid + 1\n",
    "\n",
    "        elif target < nums[mid]:\n",
    "            right_idx = mid - 1\n",
    "        else:\n",
    "            return mid\n",
    "\n",
    "    if target > nums[left_idx]:\n",
    "        return left_idx + 1\n",
    "    else:\n",
    "        return left_idx\n",
    "      \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        left = 0\n",
    "        right = len(nums) - 1\n",
    "        while left <= right:\n",
    "            middle = (left + right) // 2\n",
    "            if nums[middle] == target:\n",
    "                return middle\n",
    "            elif nums[middle] > target:\n",
    "                right = middle - 1\n",
    "            elif nums[middle] < target:\n",
    "                left = middle + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "\n",
    "    n = len(nums)\n",
    "    left_idx = 0\n",
    "    right_idx = n - 1\n",
    "       \n",
    "    if target < nums[left_idx]:\n",
    "        return left_idx\n",
    "    \n",
    "    elif target > nums[right_idx]:\n",
    "        return right_idx + 1\n",
    "\n",
    "    while left_idx < right_idx:\n",
    "        mid = left_idx + (right_idx - left_idx) // 2\n",
    "\n",
    "        if target > nums[mid]:\n",
    "            left_idx = mid + 1\n",
    "\n",
    "        elif target < nums[mid]:\n",
    "            right_idx = mid - 1\n",
    "        else:\n",
    "            return mid\n",
    "\n",
    "    if target > nums[left_idx]:\n",
    "        return left_idx + 1\n",
    "    else:\n",
    "        return left_idx\n",
    "      \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        left, right, ans = 0, len(nums)-1, 0\n",
    "        while left <= right:\n",
    "            mid = (left+right) //2\n",
    "            if nums[mid] == target:\n",
    "                return mid\n",
    "            elif nums[mid] > target:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                ans = mid + 1\n",
    "                left = mid + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        left, right = 0, len(nums)-1\n",
    "        while left <= right:\n",
    "            mid = (left+right) //2\n",
    "            if nums[mid] == target:\n",
    "                return mid\n",
    "            elif nums[mid] > target:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        return bisect_left(nums,target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "           n=0\n",
    "           if nums is None:\n",
    "                  return 0\n",
    "           if nums[len(nums)-1]<target:\n",
    "                  return len(nums)\n",
    "           for i in range(len(nums)):\n",
    "                  if nums[i]>=target:\n",
    "                     n=i\n",
    "                     break\n",
    "           if nums[n-1]==target:\n",
    "                   return n\n",
    "           else:return n \n",
    "           \n",
    "           \n",
    "           \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        return bisect_left(nums, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 满足二分查找的前提，即有序数组+无重复元素+返回下标，但是和二分法不同的是，之前的二分法只需要返回下标即可，但是这里的二分法还要求“如果不存在于数组则返回被插入的位置”，所以这里应该用左闭右开的写法，中间如果找到就return middle，while结束后return left。二分查找的时间复杂度为logn，满足这里的要求。\n",
    "\n",
    "# 左闭右开区间，边界条件为while left<right，赋值语句为if nums[middle] > target，right == middle，且right的初始位置为len(nums)(因为right不包含)\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        if len(nums) == 0:  # 注意这个别忘 # 1\n",
    "            return -1 # 2\n",
    "        left, right = 0, len(nums) # 3\n",
    "        while left < right: # 4\n",
    "            middle = left + (right - left) // 2 \n",
    "            # 注意取middle的方法要记住！！！且python中除除以2取除数的符号是\"//\"\n",
    "            if nums[middle] == target:  # 6 \n",
    "                return middle # 7\n",
    "            elif nums[middle] > target: # 返回左区间 # 8\n",
    "                right = middle # 9\n",
    "            else: # 返回右区间 # 10\n",
    "                left = middle + 1 # \n",
    "        return left   # 5\n",
    "         # 最后的return值表示如果没找到那么应该返回什么，这里因为要求返回插入位置的下标，所以返回left，否则对于常规二分法来说这里返回的应该是-1\n",
    "\n",
    "# 注意：对于仅要求返回下标的基础二分法来说，左闭右闭区间的写法和上面的区别是：right的初始位置为len(nums)-1(因为right包含)；边界条件为while left <= right；赋值语句为if nums[middle] > target，right == middle - 1(因为right包含)\n",
    "# 不论是写法1还是写法2，当nums[middle] < target，即要跳转到右区间时，赋值语句都应该为left=middle + 1(因为left一直都是被包含在区间内的)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        left = 0\n",
    "        right = len(nums) - 1\n",
    "        while left <= right:\n",
    "            mid = (left + right)//2\n",
    "            if nums[mid] > target:\n",
    "                ans = mid\n",
    "                right = mid - 1\n",
    "            elif nums[mid] < target:\n",
    "                ans = mid + 1\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                return mid\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        left, right = 0, len(nums)-1\n",
    "        while left <= right:\n",
    "            mid = (left+right) // 2\n",
    "            if nums[mid] == target:\n",
    "                return mid\n",
    "            elif nums[mid] > target:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        i , j = 0, len(nums) - 1\n",
    "        while i <= j:\n",
    "            m = (i + j) // 2\n",
    "            if nums[m] > target:\n",
    "                j = m - 1\n",
    "            elif nums[m] < target:\n",
    "                i = m + 1\n",
    "            else:\n",
    "                return m\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        l = r = 0\n",
    "        if target in nums:\n",
    "            return nums.index(target)\n",
    "        else:\n",
    "            if target > nums[-1]:\n",
    "                return len(nums)\n",
    "            if target < nums[0]:\n",
    "                return 0\n",
    "            else:\n",
    "                a = [i for i,x in enumerate(nums) if x > target]\n",
    "                return a[0]\n",
    "\n",
    " \n",
    "            \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
